The Forward z-Transform

Before we get into the details of the rule bases, we define the z- and discrete-time Fourier transforms. The forward z-transform produces an analytic function X(z), from a sequence x[n]:

#math219#
X(z) = #tex2html_wrap_indisplay3038#{x[n]} = #tex2html_wrap_indisplay3039#x[n]z-n (1)
[Oppenheim and Schafer 1989]. (The bilateral version of the z- and Laplace transforms was adopted in these packages because it commonly used in signal processing. The unilateral form, where the sum extends only over non-positive n, is sometimes better suited to solving initial-value problems; but the bilateral form can also handle initial conditions by means of delta and step functions.)

The sum in (1) converges for values of z in a region of the form #math220#{z : r- ;SPMlt; | z| ;SPMlt; r+}, that is, an annulus (r- and r+ are both finite), an open disc (r- = 0 and r+ is finite), the complement of a closed disc or the whole plane. This information is found and preserved by 56:

<#3048#> 
verbatim179#
<#3048#>

In this way, information about the stability of a signal can be obtained. (A signal is called <#1160#>stable<#1160#> if the sum of its absolute values remains bounded as time increases.) The function <#241#>Stable<#241#> operates on the z-transform of a digital signal, returning <#242#>True<#242#> if the signal is stable and <#243#>False<#243#> otherwise. If the stability is dependent on values of free parameters, <#244#>Stable<#244#> returns a set of stability conditions:

<#3050#> 
verbatim180#
<#3050#>

The multidimensional z-transform is obtained by applying the one-dimensional z-transform once for each dimension. For example, the two-dimensional z-transform #math221#X(z1, z2) of the function #math222#x[n1, n2] is defined as

#math223#
X(z1, z2) = #tex2html_wrap_indisplay3060##tex2html_wrap_indisplay3061#x[n1, n2]z1-n1z2-n2 (2)
  = #tex2html_wrap_indisplay3064##tex2html_wrap_indisplay3065##tex2html_wrap_indisplay3066#x[n1, n2]z1-n1#tex2html_wrap_indisplay3067#z2-n2  
  = #tex2html_wrap_indisplay3072#n2{#tex2html_wrap_indisplay3075#n1{x[n1, n2]}}  

[Dudgeon and Mersereau 1984]. However, care must be taken in computing the region of convergence. If the function #math224#x[n1, n2] is <#1161#>separable<#1161#>, that is, a product of functions of the two variables separately, the region of convergence of the double series (2) is the Cartesian product of the regions of convergence of the series (1) for the factors. For a non-separable function, however, this is not so, and we must take that into account.

The 57 function requires two arguments: the function to be transformed and the name of the ``time'' variable(s). The second argument determines the dimensionality and makes all other symbols in the expression to be treated as constants. An optional third argument allows the user to specify the names of the transform variable(s); the default is 58 in one dimension and 59 in several. Any other arguments are treated as options. Currently there are only two options, 60 (explained in Appendix A) and 61. Setting 62 to 63 causes the program to tell the user about what strategies are being employed, and what functions, if any, could not be transformed. This is the default option. 64 can also be set to <#271#>False<#271#> (no justification) or <#272#>All<#272#> (complete justification). The <#273#>All<#273#> setting causes each step of the transformation to be displayed, so it is useful for teaching the mechanics of taking the z-transform.

65 works by calling a one-dimensional rule base, <#274#>MyZTransform<#274#>, once for each variable to be transformed. The seventy-six rules in the <#275#>MyZTransform<#275#> rule base are divided into six groups, as shown in Table 4. The first group is needed in order to track the region of convergence of non-separable functions.

<#3099#>Table<#3099#>: <#3100#>Synopsis of rules for one-dimensional forward z-transforms<#3100#>
Type of rule Number Table
multidimensional hooks 9 ;SPMnbsp;
rational transform pairs 15 5
non-rational transform pairs 7 6
transform properties 13 7
transforms of operators 22 8
transform strategies 10 9


The next two groups encode rational (see Table 5) and non-rational (see Table 6) transform pairs. These rules apply to terms that contain either an impulse or a step function, so that every term is one-sided. Only right-sided transform pairs are encoded because special rules exist that take the left-sided transform by reversing the sequence in time, finding the transform, and then adjusting the result.


<#3104#>Table<#3104#>: <#3105#>Rational z-transform pairs; adapted from [Muth 1978] and [Oppenheim and Schafer 1989].<#3105#>
#table284#



<#3109#>Table<#3109#>: <#3110#>Non-rational z-Transform Pairs. The last transform pair is from [Clements and Pease 1989]; all others are from [Muth 1978].<#3110#>
#table331#


The next group of rules implements the properties of the z-transform listed in Table 7. For example, the shift property

#math225#

#tex2html_wrap_indisplay3116#{x[n + m]} = zm#tex2html_wrap_indisplay3117#{x[n]}

is implemented by the (somewhat simplified) rules 
verbatim181#

The first rule is for right-sided (causal) sequences, and the second is for left-sided (anti-causal) sequences; thus the pattern <#359#>f_ Step[m_ - n_]<#359#> matches anti-causal functions such as <#360#>Cos[Pi k / 5] Step[3 - k]<#360#>, where <#361#>k<#361#> is the variable being transformed. The third rule transforms shifted impulses. The <#362#>z66m<#362#> term has been factored out in all three rules.

The fifth section of <#363#>MyZTransform<#363#> takes the z-transform of different operators, according to Table 8. Because this rule base is recursive, <#364#>z-transform<#364#>s of cascaded systems can be found---~~for example, the z-transform of an upsampled, time-reversed, impulse response of an FIR filter.

<#3121#>Table<#3121#>: <#3122#>z-Transforms of operators: adapted from [Muth 1978] and [Oppenheim and Schafer 1989].<#3122#>
#table365#


The last group of rules (Table 9) adds strategies to try if all preceding rules have failed to give the transform completely. The repeated application of any of the starred strategy rules will cause an infinite loop, so local state information is associated with every expression (and inherited by every sub-expression) to prevent each of these rules from being applied more than once. The local state information is implemented as a list of five boolean values, one for each critical rule.

<#3126#>Table<#3126#>: <#3127#>Strategies for forward z-transforms. An asterisk means that once the rule is applied to an expression, it will no longer be applied to any part of that expression.<#3127#>
#table396#